/*
题目：二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：

    展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
    展开后的单链表应该与二叉树 先序遍历 顺序相同。
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
 */
public class Flatten {
    public void flatten(TreeNode root) {
        if (root == null)   return ;
        Stack<TreeNode> stack = new Stack<> ();
        TreeNode prev = null;//记录刚走过的上一个节点
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (prev != null) {
                prev.left = null;
                prev.right = cur;
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }

            prev = cur;
        }
    }
}
